package com.origin.niuke.recursion;

import java.util.ArrayList;

/**
 * 汉诺塔问题
 * 算法：递归
 * 步骤
 * 1、将 n - 1 个盘子从 left 借助 right 移到 mid 上
 * 2、将第 n 个盘子从 left 移到 right 上
 * 3、剩下的 n - 1 个盘子从 mid 借助 left 移到 right 上
 *
 * @author yezh
 * @date 2022/12/28 14:28
 */
public class NC67 {

    ArrayList<String> ans;
    public ArrayList<String> getSolution(int n) {
        ans = new ArrayList<>();
        hanoi(n, "left", "mid", "right");
        return ans;
    }

    void hanoi(int n, String left, String mid, String right) {
        if (n == 0) return;
        hanoi(n - 1, left, right, mid);
        ans.add("move from " + left + " to " + right);
        hanoi(n - 1, mid, left, right);
    }

}
